package leetcode20211005;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LUYAO
 * Date: 2021-10-05
 * Time: 12:36
 */
public class MaxGiftRoute {
    public static void main(String[] args) {

    }
}

class Solution2 {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;

        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        //多开一行一列，不改变原来，更简洁。
        int[][] dp = new int[row + 1][column + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= column; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][column];
    }
}
